/**
 * 归并排序算法实现
 * 该程序实现了归并排序算法，用于对整数数组进行排序
 * 归并排序是一种分治算法，时间复杂度为O(n log n)
 */

#include <iostream>
#include <vector>

/**
 * 合并两个已排序的数组
 * @param left 左半部分已排序数组
 * @param right 右半部分已排序数组
 * @return 合并后的已排序数组
 */
std::vector<int> merge(std::vector<int> left, std::vector<int> right) {
    std::vector<int> result;  // 存储合并后的结果
    int i = 0, j = 0;         // i和j分别是左右数组的索引
    
    // 比较左右两个数组的元素，将较小的元素放入结果数组
    while (i < left.size() && j < right.size()) {
        if (left[i] < right[j]) {
            result.push_back(left[i]);  // 左数组元素较小，加入结果
            i++;                        // 左数组索引加1
        } else {
            result.push_back(right[j]); // 右数组元素较小，加入结果
            j++;                        // 右数组索引加1
        }
    }
    
    // 处理左数组中剩余的元素
    while (i < left.size()) {
        result.push_back(left[i]);
        i++;
    }
    
    // 处理右数组中剩余的元素
    while (j < right.size()) {
        result.push_back(right[j]);
        j++;
    }
    
    return result;  // 返回合并后的数组
}

/**
 * 归并排序函数
 * @param arr 待排序的数组
 * @return 排序后的数组
 */
std::vector<int> merge_sort(std::vector<int> arr) {
    // 基本情况：如果数组长度小于等于1，直接返回
    if (arr.size() <= 1) {
        return arr;
    }
    
    // 计算数组的中点
    int mid = arr.size() / 2;
    
    // 将数组分为左右两部分
    std::vector<int> left(arr.begin(), arr.begin() + mid);   // 左半部分
    std::vector<int> right(arr.begin() + mid, arr.end());    // 右半部分
    
    // 递归地对左右两部分进行排序
    left = merge_sort(left);    // 对左半部分进行归并排序
    right = merge_sort(right);  // 对右半部分进行归并排序
    
    // 合并两个已排序的部分
    return merge(left, right);
}

/**
 * 主函数
 * 演示归并排序的使用
 */
int main() {
    // 初始化一个未排序的数组
    std::vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    
    // 调用归并排序函数对数组进行排序
    std::vector<int> sorted_arr = merge_sort(arr);
    
    // 输出排序后的数组
    for (int num : sorted_arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
} 